package com.example.dynamicplanning;

import java.util.Arrays;

/**
 * 300.最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * 示例 1：
 * 
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 * 
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 */
public class Solution300 {

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{10,9,2,5,3,7,101,18,299}));
    }

    public static int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                /** 两个for表示的是数组从j～i的区间，如果i下标值>j下标值，那么更新dp[i]，取d[i]和d[j]+1的最大值（d[i]代表以前的最大值，d[j]+!
                 代表当前轮次的子序列长*/
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }




    /**
     * retrun the longest increasing subsequence
     *
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS(int[] arr) {
        int n = arr.length;
// 列表的最大子序列 下标从1开始
        int[] end = new int[n + 1];
// 存储每个元素的最大子序列个数
        int[] dp = new int[n];
        int len = 1;
//子序列的第一个元素默认为数组第一个元素
        end[1] = arr[0];
//第一个元素的最大子序列个数肯定是1
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            if (end[len] < arr[i]) {
//当arr[i] > end[len] 时 arr[i]添加到 end后面
                end[++len] = arr[i];
                dp[i] = len;
            } else {
// 当前元素小于end中的最后一个元素 利用二分法寻找第一个大于arr[i]的元素
// end[l] 替换为当前元素 dp[]
                int l = 0;
                int r = len;
                int i1 = Arrays.binarySearch(end, l, r, arr[i]);
                System.out.println(i1);
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (end[mid] >= arr[i]) {
                        r = mid - 1;
                    } else l = mid + 1;
                }
                end[l] = arr[i];
                dp[i] = l;
            }
        }


        int[] res = new int[len];
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }
}


